Главная arrow книги arrow Копия Глава 6. Поиск в условиях противодействия arrow Прекращение поиска
Прекращение поиска

До сих пор речь шла о том, что прекращение поиска на определенном уровне и выполнение альфа-бета-отсечения, по-видимому, не влияет на результат. Существует также возможность выполнять предварительное отсечение, а это означает, что некоторые ходы в данном конкретном узле отсекаются немедленно, без дальнейшего рассмотрения. Очевидно, что большинство людей, играющих в шахматы, рассматривают лишь несколько ходов из каждой позиции (по крайней мере, сознательно). К сожалению, этот подход является довольно опасным, поскольку нет никакой гарантии того, что не произойдет отсечение лучшего хода. А если отсечение применяется недалеко от корня, результат может оказаться катастрофическим, поскольку слишком часто возникают такие ситуации, что программа пропускает некоторые "очевидные" ходы. Предварительное отсечение может использоваться безопасно в особых ситуациях (например, если два хода являются симметричными или эквивалентными по каким-то другим признаками, то необходимо рассматривать только один из них) или при анализе узлов, которые находятся глубоко в дереве поиска.

В результате совместного использования всех методов, описанных выше, появляется возможность создать программу, которая неплохо играет в шахматы (или другие игры). Предположим, что реализована функция оценки для шахмат, предусмотрена разумная проверка останова в сочетании с поиском спокойной позиции, а также предусмотрена большая таблица транспозиций. Кроме того, предположим, что, затратив целые месяцы на скрупулезную разработку программ, функционирующих на уровне битов, мы получили возможность формировать и оценивать примерно миллион узлов в секунду на новейшем персональном компьютере, что позволяет выполнять поиск приблизительно среди 200 миллионов узлов в расчете на каждый ход при стандартном контроле времени (три минуты на каждый ход). Коэффициент ветвления для шахмат составляет в среднем примерно 3 5, а равно приблизительно 50 миллионам, поэтому при использовании минимаксного поиска мы получим возможность заглядывать вперед лишь приблизительно на пять полуходов. Такая программа, хотя и не совсем некомпетентная, может быть легко обманута человеком, игроком в шахматы среднего уровня, который иногда способен планировать на шесть или восемь полуходов вперед. Альфа-бета-поиск позволяет достичь глубины приблизительно в 10 полуходов, что приводит к усилению игры до уровня мастера. В разделе 6.7 описаны дополнительные методы отсечения, которые позволяют увеличить эффективную глубину поиска примерно до 14 полуходов. Чтобы достичь уровня гроссмейстера, требуется тщательно настроенная функция оценки и большая база данных с записями оптимальных ходов в дебюте и эндшпиле. Не мешало бы также иметь суперкомпьютер для эксплуатации на нем такой программы!